package batchjob;

/** This class implements the well-know quicksort algorithm for a number of
    datatypes.
 */
public class RKUQuickSort
{

  /** Quicksort an integer array in ascending order. 
      @param thearray The array to sort.
  */
  public static void quickSort(int[] thearray)
    {
      quickSortInt(thearray, 0, thearray.length);
    }
  
  /** Quicksort an int array in ascending order. <br>
      To sort the whole array use lowerindex = 0 and 
      upperindex = thearray.length
      @param thearray The array to sort.
      @param lowerindex The lower index in thearray.
      @param upperindex The upper index in thearray + 1. 
  */
  public static void quickSort(int[] thearray, int lowerindex, int upperindex)
    {
      quickSortInt(thearray, lowerindex, upperindex);
    }
  
  private static void quickSortInt(int[] thearray, int L, int R)
    {
      int splitit;
      int splitres;
      int theint;
      
      if (L<R-1)
	{
	  splitit = L+((int)(Math.rint((R-L)*Math.random()))%(R-L));
	  splitres = opdelInt(thearray,L,R,thearray[splitit]);
	  if(splitit<splitres)
	    {
	      splitres--;
	    }
	  theint = thearray[splitit];
	  thearray[splitit] = thearray[splitres];
	  thearray[splitres] = theint;
	  quickSortInt(thearray,L,splitres);
	  quickSortInt(thearray,splitres+1,R);
	};
    };
  
  private static int opdelInt(int[] thearray,int b, int e, int val)
    {
      int theint;
      while (b<e)
	{
	  if (thearray[b]<=val)
	    {
	      b++;
	    }
	  else if ((thearray[e-1]<val) && (val<thearray[b]))
	    {
	      theint = thearray[b];
	      thearray[b] = thearray[e-1];
	      thearray[e-1] = theint;
	      b++;
	      e--;
	    }
	  else if (val<=thearray[e-1])
	    {
	      e--;
	    };
	}
      return b;
    }

  // **************************************************************************
  // **************************************************************************

  /** Quicksort a double array in ascending order. 
      @param thearray The array to sort.
  */
  public static void quickSort(double[] thearray)
    {
      quickSortDouble(thearray, 0, thearray.length);
    }


  /** Quicksort a double array in ascending order. <br>
      To sort the whole array use lowerindex = 0 and 
      upperindex = thearray.length
      @param thearray The array to sort.
      @param lowerindex The lower index in thearray.
      @param upperindex The upper index in thearray + 1. 
  */
  public static void quickSort(double[] thearray, int lowerindex, int upperindex)
    {
      quickSortDouble(thearray, lowerindex, upperindex);
    }


  private static void quickSortDouble(double[] thearray, int L, int R)
    {
      int splitit;
      int splitres;
      double thedouble;

      if (L<R-1)
	{
	  splitit = L+((int)(Math.rint((R-L)*Math.random()))%(R-L));
	  splitres = opdelDouble(thearray,L,R,thearray[splitit]);
	  if(splitit<splitres)
	    {
	      splitres--;
	    }
	  thedouble = thearray[splitit];
	  thearray[splitit] = thearray[splitres];
	  thearray[splitres] = thedouble;
	  quickSortDouble(thearray,L,splitres);
	  quickSortDouble(thearray,splitres+1,R);
	};
    };
  
  private static int opdelDouble(double[] thearray,int b, int e, double val)
    {
      double thedouble;
      while (b<e)
	{
	  if (thearray[b]<=val)
	    {
	      b++;
	    }
	  else if ((thearray[e-1]<val) && (val<thearray[b]))
	    {
	      thedouble = thearray[b];
	      thearray[b] = thearray[e-1];
	      thearray[e-1] = thedouble;
	      b++;
	      e--;
	    }
	  else if (val<=thearray[e-1])
	    {
	      e--;
	    };
	}
      return b;
    }

  // **************************************************************************
  // **************************************************************************

  /** Quicksort an object array in ascending order. This method assumes
      that the object in the array implements the interface RKUOrdering.
      @param thearray The array to sort.
  */
  public static void quickSort(Object[] thearray)
    {
      quickSortObject(thearray, 0, thearray.length);
    }

  /** Quicksort a part of an object array in ascending order. 
      This method assumes that the object in the array implements the 
      interface RKUOrdering. <br>
      To sort the whole array use lowerindex = 0 and 
      upperindex = thearray.length
      @param thearray The array to sort.
      @param lowerindex The lower index in thearray.
      @param upperindex The upper index in thearray + 1. 
  */
  public static void quickSort(Object[] thearray, int lowerindex, int upperindex)
    {
      quickSortObject(thearray, lowerindex, upperindex);
    }


  private static void quickSortObject(Object[] thearray, int L, int R)
    {
      int splitit;
      int splitres;
      Object theObject;

      if (L<R-1)
	{
	  splitit = L+((int)(Math.rint((R-L)*Math.random()))%(R-L));
	  splitres = opdelObject(thearray,L,R,thearray[splitit]);
	  if(splitit<splitres)
	    {
	      splitres--;
	    }
	  theObject = thearray[splitit];
	  thearray[splitit] = thearray[splitres];
	  thearray[splitres] = theObject;
	  quickSortObject(thearray,L,splitres);
	  quickSortObject(thearray,splitres+1,R);
	};
    };
  
  private static int opdelObject(Object[] thearray,int b, int e, Object val)
    {
      Object theObject;
      while (b<e)
	{
	  if (((RKUOrdering)thearray[b]).lessOrEqual(val))
	    {
	      b++;
	    }
	  else if ((((RKUOrdering)thearray[e-1]).less(val)) && (((RKUOrdering)val).less((RKUOrdering)thearray[b])))
	    {
	      theObject = thearray[b];
	      thearray[b] = thearray[e-1];
	      thearray[e-1] = theObject;
	      b++;
	      e--;
	    }
	  else if (((RKUOrdering)val).lessOrEqual((RKUOrdering)thearray[e-1]))
	    {
	      e--;
	    };
	}
      return b;
    }

  // **************************************************************************

}
